/*
 * @lc app=leetcode.cn id=2 lang=javascript
 *
 * [2] 两数相加
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/** 逆序两数相加
 * 1. 最小单元：取两个链表的最末位进行加和，如果大于10则进1，余数放在新链表相同位置，有进位则放在新链表的下一位置
 * 2. 重复单元：遍历两个链表，直到最大长度链表遍历完成
 *    2.1 遍历链表思路：用一个指针指向当前处理节点，处理完成后下移，直到为null
 * 3. 边界处理：
 *    1. 较短链表可能为null,为null则不下移
 *    2. 如果最高位进位，也需要存储
 * 4. 时间复杂度：n；空间复杂度：n
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  // 1. 创建个新链表用于存储结果
  const l3 = new ListNode(0);
  // 2. 准备遍历链表
  let p1 = l1;
  let p2 = l2;
  let p3 = l3;
  //   3. 准备进位变量
  let carry = 0;
  //   开始遍历，直到所有链表均终止才停止遍历
  while (p1 || p2) {
    // 边界处理：较短链表可能为null
    const v1 = p1 ? p1.val : 0;
    const v2 = p2 ? p2.val : 0;
    const val = v1 + v2 + carry;
    carry = Math.floor(val / 10);
    // 结果存储
    p3.next = new ListNode(val % 10);
    // 下移所有链表指针
    // 边界处理：较短链表可能为null，为null则不下移
    if (p1) {
      p1 = p1.next;
    }
    if (p2) {
      p2 = p2.next;
    }
    p3 = p3.next;
  }
  //   边界处理，如果最高位进位，也需要存储
  if (carry) {
    p3.next = new ListNode(carry);
  }
  return l3.next;
};
// @lc code=end
